package 力扣_算法题综合.高频面试算法;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @author zx
 * @create 2022-10-20 18:36
 * 源于LinkedHashMap源码的版本,好写且理解了LinkedHashMap
 * https://leetcode.cn/problems/lru-cache/solution/yuan-yu-linkedhashmapyuan-ma-by-jeromememory/
 * 厉害,LinkedHashMap源码分析这一波真的厉害
 *
 */
public class LRU缓存_146_II extends LinkedHashMap<Integer,Integer> {
    private int capacity;

    /**
     * @param capacity 构造器方法
     * initialCapacity代表map的容量,loadFactor代表加载因子(默认即可)
     * accessOrder默认是为false,如果要按读取顺序排序需要将其设为true
     */
    public LRU缓存_146_II(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    /**
     * @return 题目要求：如果关键字key存在于缓存中,则返回关键字的值,否则返回-1.
     * LinkedHashMap中此方法的作用：
     * 返回指定键映射到的值,如果该映射不包含键的映射,则返回defaultValue
     */
    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    // 这个可不写:很明显我们只需要直接继承父类的put函数即可,因为题目没有特殊要求
    /**
     * @return 题目要求：如果关键字key已经存在,则变更其数据值value;如果不存在
     * 则向缓存中插入该组key-value. 如果插入操作导致关键字数量超过capacity, 则应该逐出最久未使用的关键字
     *
     * 如果是按照读取顺序排序,即调用afterNodeAccess()完成,这个就是著名的LRU算法
     * 插入新节点才会触发afterNodeInsertion(boolean evict)
     * 根据 HashMap的putVal方法, evict一直是true
     * afterNodeInsertion()根据条件判断是否移除最近最少被访问的节点
     * removeEldestEntry方法表示移除规则,在LinkedHashMap里一直返回false
     * 所以在 LinkedHashMap 里这个方法相当于什么都不做
     *
     */
    public void put(int key, int value) {
        super.put(key, value);
    }

    /**
     * @return 缓存策略方法,fterNodeInsertion()内部会调用
     *
     * 移除最近最少被访问条件之一，通过覆盖此方法可实现不同策略的缓存
     * removeEldestEntry方法表示移除规则,在LinkedHashMap里一直返回false
     * 所以在LinkedHashMap 里这个方法相当于什么都不做
     * 要满足本题题意配置缓存策略:(如果插入操作导致关键字数量超过capacity
     * 则应该逐出最久未使用的关键字)可以继承LinkedHashMap然后复写该方法
     * 直接return size() > capacity;
     */
    @Override
    public boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return super.size() > capacity;
    }
}
